package jianzhioffer;

// 剑指 Offer 53 - II. 0～n-1中缺失的数字
public class MissingNumber {


    public static void main(String[] args) {
        int[] data = {0,1,2,3,6,7};
        System.out.println(missingNumber(data));
    }
    public static int missingNumber(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (nums[mid] != mid) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }


    // 暴力
    public int missingNumber2(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i) {
                return i;
            }
        }
        return nums.length;
    }
}
